package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/degree-of-an-array/'>数组的度(Degree of an Array)</a>
 * <p>给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。</p>
 * <p>你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,2,2,3,1]
 *      输出：2
 *      解释：
 *          输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
 *          连续子数组里面拥有相同度的有如下所示：
 *          [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
 *          最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
 *
 * 示例 2：
 *      输入：nums = [1,2,2,3,1,4,2]
 *      输出：6
 *      解释：
 *          数组的度是 3 ，因为元素 2 重复出现 3 次。
 *          所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>nums.length 在 1 到 50,000 范围内。</li>
 *         <li>nums[i] 是一个在 0 到 49,999 范围内的整数。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/18 13:25
 */
public class LC0697DegreeOfArray_S {
    static class Solution {
        public int findShortestSubArray(int[] nums) {
            Map<Integer, int[]> map = new HashMap<>();
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (map.containsKey(nums[i])) {
                    map.get(nums[i])[0]++;
                    map.get(nums[i])[2] = i;
                } else {
                    map.put(nums[i], new int[]{1, i, i});
                }
            }
            int maxNum = 0;
            int minLen = 0;
            for (int[] ints : map.values()) {
                // ints[0]：当前数字出现的次数
                // ints[1]：当前数字第一次出现的位置
                // ints[2]：当前数字最后一次出现的位置
                int times = ints[0];
                // 前后位置差
                int length = ints[2] - ints[1] + 1;
                if (times > maxNum) {
                    maxNum = times;
                    minLen = length;
                } else if (times == maxNum && length < minLen) {
                    minLen = length;
                }
            }
            return minLen;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findShortestSubArray(new int[]{1, 2, 2, 3, 1}));
        System.out.println(solution.findShortestSubArray(new int[]{1, 2, 2, 3, 1, 4, 2}));
    }
}
